The following abbreviations are herewith defined, at least some of which are referred to within the following description of the state-of-the-art and the present invention.
BPDU Bridge Protocol Data Unit
CE Customer Edge (device)
IEEE Institute of Electrical and Electronics Engineers
IETF Internet Engineering Task Force
ITU International Telecommunication Union
LACP Link Aggregation Control Protocol
LAG Link Aggregation
LAN Local Area Network
LDP Label Distribution Protocol
MAC Media Access Control
MC-LAG Multi-Chassis Link Aggregation
MPLS Multiprotocol Label Switching
MSTP Multiple Spanning Tree Protocol
PDB Permanent Database
PDU Protocol Data Unit
PE Provider Edge (device)
RFC Request for Comments (an IETF publication) RSTP Rapid Spanning Tree Protocol
STP Spanning Tree Protocol
VLAN Virtual Local Area Network
VPLS Virtual Private LAN Service
Computers are often connected together through a communications network that can be used to transmit data from its origin to one or more intended destination. In many such networks, the data is first broken up into discrete segments, often referred to as packets or frames. Individual segments are addresses and sequentially numbered so that they may be reassembled at the destination node. The origin and destination nodes are not usually connected directly to each, so the data must be routed though the various network nodes. A typical network is made up of many nodes, such as bridges or routers, which receive and forward the data packets or frames toward their destination. The network nodes are typically interconnected in such a way that the individual data segments making up a transmission may take more than one route. This form of interconnection aids in providing reliable transmission even when some of the paths or nodes fail as happens from time to time.
One type of computer network is a LAN, which may be implemented by a business or other enterprise to tie together some or all of the computers at a given location. Many LANs also include some type of gateway node to permit communication with entities outside of the LAN itself, for example providing Internet access to LAN users. In some cases a business may have more than one location, each with its own LAN. When this occurs, there is naturally a desire to connect the two (or more) LANs together so that LAN users in each location can communicate with those in other locations. Simply communicating through a widely-accessible network might pose security risks, so enhanced methods have been developed.
Once such method is VPLS, a protocol described in part in RFC 4762, promulgated by the IETF. VPLS creates an emulated Ethernet LAN segment that is accessible to some users but not to others, though a large network that is often referred to as a VPLS core or simply a “cloud” (in reference to the manner is which it is often represented in illustrations). This VPLS network is often owned by a network service provider, who uses it to provide VPLS services to many customers. A customer, such as the business referred to above, may, for example, connect two LANS through the VPLS core. Each LAN and the VPLS core interface with each other at respective customer or provider edge devices.
A single CE device from each LAN may attach to a single proximate PE device, although an attachment scheme known as dual homing has also been developed. In a dual homing topology, two ports on the CE device are allocated to the VPLS interface, with each allocated port being placed into communication with a different PE device. Dual homing provides, among other advantages, a redundant connection to the VPLS or other network that may prove useful if a link failure occurs.
Unfortunately, in this topology loops can occur, where nodes that are used to route data will potentially receive packets or frames that they have already transmitted, and must then attempt again to forward them toward their destination. This creates a large inefficiency, and solutions have been created to prevent loops from happening. One solution is knows as spanning tree protocol, or STP. STP is described in IEEE 802.1 D and related standards. It is currently widely used in its more recent formulations, such as RSTP and MSTP (described in IEEE 802.1w and 802.1s, respectively). The term xSTP is sometimes used to generally refer to all of these variations.
In general, STP prevents loops in a network by establishing one primary pathway between any two network nodes. Communicating through messages known as BPDUs, the network nodes determine a root node and for each spanning tree, compute the pathways, and then block transmissions on other paths. The protocols also allow for the detections of the failure of a primary pathway and calculation of any necessary adjustments. This adjustment is often referred to as re-convergence and generally involves not only calculating the new pathways, but blocking and unblocking the links necessary to put the new spanning tree into effect.
A VPLS network may be expected to have xSTP implemented for loop prevention within the VPLS core. This frequently does not, however, detect loops through the provider network involving the CE device in a dual homing configuration, which means the CE must run its own loop avoidance protocol. Unfortunately, current standards do not guarantee that re-convergence after a failure in the dual homing topology will occur quickly. For example, a desirable re-convergence time for VPLS core nodes is currently below 50 ms, but an instance of xSTP running on a CE attached to the VPLS core may not be able to effect re-convergence in under 3 seconds, and it may perhaps take as long as 30 seconds. This is especially true where, as is frequently the case, the CE device is running one proprietary version of xSTP and the provider nodes are running another.
Accordingly, there has been and still is a need to address the aforementioned shortcomings and other shortcomings associated with re-convergence after failure in a dual homing environment. These needs and other needs are satisfied by the present invention.